#include <algorithm>
#include <filesystem>
#include <iostream>
#include <queue>
#include <ranges>
#include <unordered_map>
#include <vector>
using namespace std;
// class Solution {
// public:
//     vector<int> spiralOrder(vector<vector<int>>& matrix) {
//         std::vector<int> res;
//         //获取行列数
//         int row = matrix.size();
//         int col = matrix[0].size();
//         //定义上下左右边界
//         int top = 0;
//         int bottom = row - 1;
//         int left = 0;
//         int right = col - 1;
//
//         while (top <= bottom && left <= right) {
//             //从左到右
//             for (int i = left; i <= right; i++) {
//                 res.push_back(matrix[top][i]);
//             }
//             top++;
//             //从上到下
//             for (int i = top; i <= bottom; i++) {
//                 res.push_back(matrix[i][right]);
//             }
//             right--;
//             //从右到左
//             if(top > bottom) break;
//             for (int i = right; i >= left; i--) {
//                 res.push_back(matrix[bottom][i]);
//             }
//             bottom--;
//             //从下到上
//             if(left > right) break;
//             for (int i = bottom; i >= top; i--) {
//                 res.push_back(matrix[i][left]);
//             }
//             left++;
//         }
//         return res;
//     }
// };

// class Solution {
// public:
//     void rotate(vector<vector<int>>& matrix) {
//         for (int i = 0; i < matrix.size(); i++) {
//             for (int j = i+1; j < matrix.size(); j++) {
//                 if (i<j) {
//                     // int tmp = matrix[i][j];
//                     // matrix[i][j] = matrix[j][i];
//                     // matrix[j][i] = tmp;
//                     std::swap(matrix[i][j], matrix[j][i]);
//                 }
//             }
//         }
//         for (int i = 0; i < matrix.size(); i++) {
//             std::reverse(matrix[i].begin(), matrix[i].end());
//         }
//     }
// };
// void printMatrix(const vector<vector<int>>& matrix) {
//     for (const auto& row : matrix) {
//         for (int val : row) {
//             cout << val << ' ';
//         }
//         cout << '\n';
//     }
// }

// class Solution {
// public:
//     bool searchMatrix(vector<vector<int>>& matrix, int target) {
//         int right = matrix[0].size() - 1;
//         int row = 0;
//         while (right >= 0 && row < matrix.size()) {
//             if (matrix[row][right] == target) {
//                 return true;
//             }
//             else if (matrix[row][right] > target) {
//                 right -= 1;
//             }
//             else {
//                 row += 1;
//             }
//         }
//         return false;
//     }
// };

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
// class Solution {
// public:
//     ListNode *detectCycle(ListNode *head) {
//         ListNode* fast=head,*slow=head;
//         while (fast!=nullptr && fast->next!=nullptr) {
//             fast=fast->next->next;
//             slow=slow->next;
//             if (fast==slow) {
//                 // 找入环点需要让任一指针回到head位置，然后slow与head逐步向前走，再次相遇即为入环点
//                 slow = head;
//                 while (slow!=fast) {
//                     slow=slow->next;
//                     fast=fast->next;
//                 }
//                 return slow;
//             }
//         }
//         return nullptr;
//     }
// };

// select firstName,lastName,city,state from Person left join Address on Person.personId=Address.personId
// SELECT name AS Employee
// FROM Employee e1
// WHERE salary > (
//     SELECT salary
//     FROM Employee
//     WHERE id = e1.managerId
// )

// select email from Person group by email having count(email)>1
// select name as Customers from Customers
// where not exists(
//     select 1 from Orders where Customers.id=Orders.customerId
// )

// /**
//  * Definition for singly-linked list.
//  * struct ListNode {
//  *     int val;
//  *     ListNode *next;
//  *     ListNode() : val(0), next(nullptr) {}
//  *     ListNode(int x) : val(x), next(nullptr) {}
//  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
//  * };
//  */
// struct ListNode {
//     int val;
//     ListNode *next;
//     ListNode() : val(0), next(nullptr) {}
//     ListNode(int x) : val(x), next(nullptr) {}
//     ListNode(int x, ListNode *next) : val(x), next(next) {}
// };
// class Solution {
// public:
//     ListNode* swapPairs(ListNode* head) {
//         ListNode* res = head;
//         if(head && head->next){
//             res=head->next;
//         }
//         ListNode* cur = head;
//         ListNode* prev = nullptr;
//         while (cur && cur->next) {
//             ListNode* next = cur->next;
//             cur->next = next->next;
//             next->next = cur;
//             if (prev)
//                 prev->next = next;
//             prev = cur;
//             cur=cur->next;
//         }
//         return res;
//     }
// };


// // Definition for a Node.
// class Node {
// public:
//     int val;
//     Node* next;
//     Node* random;
//
//     Node(int _val) {
//         val = _val;
//         next = NULL;
//         random = NULL;
//     }
// };
//
// class Solution {
// public:
//     Node* copyRandomList(Node* head) {
//         unordered_map<Node*, Node*> m;
//         Node* curr = head;
//         Node* curNode = nullptr;
//         while (curr != nullptr) {
//             curNode = new Node(curr->val);
//             m[curr] = curNode;
//             curr = curr->next;
//         }
//         curr = head;
//         while (curr != nullptr) {
//             m[curr]->next = m[curr->next];
//             m[curr]->random = m[curr->random];
//             curr = curr->next;
//         }
//         return m[head];
//     }
// };

// #include <functional>
// struct ListNode {
//     int val;
//     ListNode *next;
//     ListNode() : val(0), next(nullptr) {}
//     ListNode(int x) : val(x), next(nullptr) {}
//     ListNode(int x, ListNode *next) : val(x), next(next) {}
// };
//
// class Solution {
// public:
//     ListNode* sortList(ListNode* head) {
//         auto cmp = [](ListNode* l1,ListNode* l2){return l1->val>l2->val;};
//         priority_queue<ListNode*,vector<ListNode*>,decltype(cmp)> pq(cmp);
//         ListNode* cur = head;
//         while (cur) {
//             pq.push(cur);
//             cur = cur->next;
//         }
//         ListNode* result = new ListNode();
//         ListNode* curr = result;
//         while (pq.size()) {
//             ListNode* node = new ListNode(pq.top()->val);
//             pq.pop();
//             curr->next = node;
//             curr = curr->next;
//         }
//         return result->next;
//     }
// };

// //LRU
// #include <List>
// class LRUCache {
// public:
//     LRUCache(int capacity)
//         :_capacity(capacity)
//     {
//
//     }
//
//     int get(int key) {
//         auto it = _cache.find(key);
//         if (it == _cache.end()) {
//             return -1;
//         }
//         //找到了
//         _keys.erase(it->second.second);
//         _keys.push_front(key); //将键移到链表头部
//         //更新_cache中迭代器位置
//         it->second.second = _keys.begin();
//
//         return it->second.first;//返回值
//     }
//
//     void put(int key, int value) {
//         auto it = _cache.find(key);
//         if (it == _cache.end()) {
//             //如果不存在,插入新的键值
//             //如果满了,要淘汰掉最久未使用的
//             if (_keys.size() == _capacity) {
//                 int last = _keys.back();
//                 _keys.pop_back();
//                 _cache.erase(last);
//             }
//             _keys.push_front(key);
//             _cache[key] = {value, _keys.begin()};
//         }else {
//             //如果存在，更改键值，并更新使用情况
//             it->second.first = value;
//             _keys.erase(it->second.second);
//             _keys.push_front(key);
//             it->second.second = _keys.begin();
//         }
//     }
// private:
//     int _capacity;
//     list<int> _keys;  // 双向链表（头部是最近使用的）
//     unordered_map<int, pair<int, list<int>::iterator>> _cache;  // 键 → (值, 链表迭代器)
// };

// template<class T>
// class shared_ptr
// {
// private:
//     //++引用计数
//     void AddRef()
//     {
//         _pmutex->lock();
//         (*_pcount)++;
//         _pmutex->unlock();
//     }
//     //--引用计数
//     void ReleaseRef()
//     {
//         _pmutex->lock();
//         bool flag = false;
//         if (--(*_pcount) == 0) //将管理的资源对应的引用计数--
//         {
//             if (_ptr != nullptr)
//             {
//                 cout << "delete: " << _ptr << endl;
//                 _del(_ptr);
//                 _ptr = nullptr;
//             }
//             delete _pcount;
//             _pcount = nullptr;
//             flag = true;
//         }
//         _pmutex->unlock();
//         if (flag == true)
//         {
//             delete _pmutex;
//         }
//     }
// public:
//     // function<void(T*)> _del = [](T* ptr) {delete ptr; };//放到私有里面
//     template<class D>
//     shared_ptr(T* ptr, D del)
//         :_ptr(ptr)
//         , _pcount(new int(1))
//         , _del(del)
//         , _pmutex(new mutex)
//     {}
//
//     // RAII
//     shared_ptr(T* ptr = nullptr)
//         :_ptr(ptr)
//         , _pcount(new int(1))
//         , _pmutex(new mutex)
//     {}
//
//     // sp2(sp1)
//     shared_ptr(const shared_ptr<T>& sp)
//         : _ptr(sp._ptr)
//         , _pcount(sp._pcount)
//         , _pmutex(sp._pmutex)
//     {
//         // 拷贝时++计数
//         AddRef();
//     }
//
//     shared_ptr<T>& operator=(const shared_ptr<T>& sp)
//     {
//         //if (this != &sp)
//         if (_ptr != sp._ptr) //管理同一块空间的对象之间无需进行赋值操作
//         {
//             ReleaseRef();        //将管理的资源对应的引用计数--
//
//             _ptr = sp._ptr;      //与sp对象一同管理它的资源
//             _pcount = sp._pcount;//获取sp对象管理的资源对应的引用计数
//             _pmutex = sp._pmutex;//获取sp对象管理的资源对应的互斥锁
//
//             // 拷贝时++计数
//             AddRef();            //新增一个对象来管理该资源，引用计数++
//         }
//
//         return *this;
//     }
//
//     ~shared_ptr()
//     {
//         // 析构时，--计数，计数减到0，
//         ReleaseRef();
//     }
//
//     int use_count()
//     {
//         return *_pcount;
//     }
//
//     // 像指针一样
//     T& operator*()
//     {
//         return *_ptr;
//     }
//
//     T* operator->()
//     {
//         return _ptr;
//     }
//
//     T* get() const
//     {
//         return _ptr;
//     }
// private:
//     T* _ptr;     // 指向动态分配对象的指针
//     int* _pcount;// 引用计数，表示当前有多少个shared_ptr指向同一个对象
//     mutex* _pmutex;// 管理的资源对应的互斥锁
//
//     function<void(T*)> _del = [](T* ptr) {delete ptr; };// 自定义删除器，默认为删除指针所指向的对象
// };

//层序遍历：队列
// class Solution {
// public:
//     vector<vector<int>> levelOrder(TreeNode* root) {
//         queue<TreeNode*> q;
//         vector<vector<int>> res;
//         if (!root) {
//             return res;
//         }
//         q.push(root);
//         while(q.size())
//         {
//             vector<int> level;
//             int levelsize = q.size();
//             for (int i=0; i<levelsize; i++) {
//                 TreeNode* node = q.front();
//                 q.pop();
//                 level.push_back(node->val);
//                 if (node->left) q.push(node->left);
//                 if (node->right) q.push(node->right);
//             }
//             res.push_back(level);
//         }
//         return res;
//     }
// };
// //层序遍历：递归
// class Solution {
// public:
//     vector<vector<int>> levelOrder(TreeNode* root) {
//         vector<vector<int>> result;
//         dfs(root, 0, result);
//         return result;
//     }
//
//     void dfs(TreeNode* node, int level, vector<vector<int>>& result) {
//         if (!node) return;  // 终止条件
//
//         if (result.size() == level) {  // 当前层尚未记录
//             result.push_back({});
//         }
//
//         result[level].push_back(node->val);  // 存入当前层
//
//         dfs(node->left, level + 1, result);   // 递归左子树
//         dfs(node->right, level + 1, result); // 递归右子树
//     }
// };

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
// //验证二叉搜索树：递归+上下界
// class Solution {
// public:
//     bool isValidBST(TreeNode* root) {
//         return isValidBSTHelper(root, LONG_MIN, LONG_MAX);
//     }
//
//     bool isValidBSTHelper(TreeNode* root, long min, long max) {
//         if (!root) return true;
//         if (root->val <= min || root->val >= max) return false;
//         return isValidBSTHelper(root->left, min, root->val) && isValidBSTHelper(root->right, root->val, max);
//     }
// };
//验证二叉搜索树：中序+前驱
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* prev = nullptr;
        return inorder(root, prev);
    }
    // 注意引用传递，否则prev = root 的修改不会传递到上层递归调用
    bool inorder(TreeNode* root, TreeNode*& prev) {
        if (!root) return true;
        if (!inorder(root->left, prev)) return false;
        if (prev && root->val <= prev->val) return false;
        prev = root;
        return inorder(root->right, prev);
    }
};
int main() {
    vector<vector<int>> mat = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    Solution().rotate(mat);
    printMatrix(mat);
    return 0;
}